Computer processors typically execute binary code encoded in a particular instruction set. Binary translation translates binary code targeted for a particular instruction set into translated binary code, generally targeted for another instruction set. Binary translation may be used to enable backward- or forward-compatibility for software applications, or to improve processing efficiency. For example, binary code targeted for a reduced instruction set computing (RISC) architecture such as PowerPC may be translated into binary code targeting a complex instruction set computing (CISC) architecture such as IA-32, allowing legacy applications to run on newer hardware. As another example, binary translation may generate translated binary code targeting the same computer architecture but optimized by using newer features such as wider instructions, improved vector instructions, or the like. Binary translation may be dynamic, that is, the code may be translated as it is executed. Certain binary translation systems may establish one or more translation caches (T-caches) to store translated binary code. A translation cache may have limited storage space, and typical binary translation systems use a least-recently-used (LRU) policy to identify translated code for eviction from the translation cache.